package offerbook;

import utils.TreeNode;

/**
 *   问题1：输入两个二叉树A、B，判断B是不是A的子结构
 *   问题2：输入两个二叉树A、B，判断B是不是A的子树
 *   注意这二者是不同的。
 *
 * 问题2更为严格 ，问题1是true问题二不一定是true。
 * 分析见笔记。
 */
public class Code18_HasSameStruct {
    public boolean HasSameStruct(TreeNode root1, TreeNode root2) {
        if(root1 == null || root2 == null) return false;
        boolean res = false;
        //if get the same label,go to judge
        if(root1.val == root2.val){
            res = process(root1,root2);
        }
        if(!res)
            res = HasSameStruct(root1.left,root2);
        if(!res)
            res = HasSameStruct(root1.right,root2);
        return res;
    }
    public boolean process(TreeNode root1, TreeNode root2) {
        //root2 == null adicate is over 
        if(root2 == null) return true;
        // assert root2 != null
        if(root1 == null) return false; 
        //assert all the root is not null
        if(root1.val != root2.val){
            return false;
        }
        return process(root1.left,root2.left)
            && process(root1.right,root2.right);
    }
}